
// 只过了80

// #include <iostream>
// #include <unordered_map>
// #include <vector>
// #include <cmath>
// using namespace std;
// unordered_map<int, int> h;
// struct DSU{
//     vector<int> parent, size;
//     DSU(int n) {
//         parent.resize(n + 1);
//         size.resize(n + 1, 1);
//         for(int i = 0; i <= n; i++) {
//             parent[i] = i;
//         }
//     }
//     int find(int x) {
//         if(parent[x] != x) {
//             parent[x] = find(parent[x]);
//         }
//         return parent[x];
//     }
//     void unite(int x, int y) {
//         int fx = find(x), fy = find(y);
//         if(fx == fy) {
//             return;
//         }
//         if(size[fx] < size[fy]) {
//             swap(fx, fy);
//         }
//         parent[fy] = fx;
//         size[fx] += size[fy]; 
//     }
// };
// // bool isPrime(int n) {
// //     if (n <= 1) return false; // 1 不是素数，0 也不是
// //     if (n == 2) return true;  // 2 是素数
// //     if (n % 2 == 0) return false; // 排除偶数（2除外）
    
// //     // 只检查到 sqrt(n)
// //     for (int i = 3; i <= sqrt(n); i += 2) {
// //         if (n % i == 0) {
// //             return false; // 如果能被整除，则不是素数
// //         }
// //     }
    
// //     return true; // 不是偶数且没有找到因数，则是素数
// // }
// vector<bool> sieve(int max_num) {
//     vector<bool> is_prime(max_num + 1, true);
//     is_prime[0] = is_prime[1] = false;
//     for (int i = 2; i * i <= max_num; i++) {
//         if (is_prime[i]) {
//             for (int j = i * i; j <= max_num; j += i) {
//                 is_prime[j] = false;
//             }
//         }
//     }
//     return is_prime;
// }
// int main() {
//     int a, b, t;
//     cin >> a >> b >> t;
//     DSU dsu(b + 2);
//     vector<bool> prime = sieve(b);
//     for(int i = a; i <= b; i++) {
//         int p = t;
//         while(p <= i) {
//             if(prime[p]) {
//                 if(i % p == 0) {
//                     if(h[p] == 0) {
//                         h[p] = i;
//                     }else {
//                         dsu.unite(h[p], i);
//                     }
//                 }
//             }
//             p++;
//         }
//     }
//     int ans = 0;
//     for(int i = a; i <= b; i++) {
//         if(dsu.parent[i] == i) {
//             ans++;
//         }
//     }
//     cout << ans << endl;
//     return 0;
// }


#include <iostream>
#include <unordered_map>
#include <vector>
#include <cmath>
using namespace std;

struct DSU {
    vector<int> parent, size;
    DSU(int n) {
        parent.resize(n + 1);
        size.resize(n + 1, 1);
        for(int i = 0; i <= n; i++) {
            parent[i] = i;
        }
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    void unite(int x, int y) {
        int fx = find(x), fy = find(y);
        if(fx == fy) return;
        if(size[fx] < size[fy]) swap(fx, fy);
        parent[fy] = fx;
        size[fx] += size[fy]; 
    }
};

vector<bool> sieve(int max_num) {
    vector<bool> is_prime(max_num + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i * i <= max_num; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= max_num; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return is_prime;
}

vector<int> get_primes_in_range(int start, int end, const vector<bool>& prime) {
    vector<int> primes;
    for(int i = max(2, start); i <= end; i++) {
        if(prime[i]) primes.push_back(i);
    }
    return primes;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int a, b, t;
    cin >> a >> b >> t;
    
    // 如果t大于b，所有数都独立
    if(t > b) {
        cout << (b - a + 1) << endl;
        return 0;
    }
    
    DSU dsu(b);
    vector<bool> prime = sieve(b);
    
    // 获取在[t, b]范围内的所有素数
    vector<int> primes = get_primes_in_range(t, b, prime);
    
    // 优化：对每个素数p，直接标记其倍数
    for(int p : primes) {
        int first_multiple = -1;
        
        // 找到第一个大于等于a的p的倍数
        int start = ((a + p - 1) / p) * p;
        
        for(int j = start; j <= b; j += p) {
            if(first_multiple == -1) {
                first_multiple = j;
            } else {
                dsu.unite(first_multiple, j);
            }
        }
    }
    
    int ans = 0;
    for(int i = a; i <= b; i++) {
        if(dsu.find(i) == i) {
            ans++;
        }
    }
    cout << ans << endl;
    
    return 0;
}